package com.msb.class03;

/**
 * @Auther: jiudianliu
 * @Date: 2024/1/27 - 01 - 27 - 14:58
 * @Description: com.msb.class03
 * @version: 1.0
 */
public class ExistNum {

    // 利用二分法在有序数组中查找局部最小值
    public static void main(String[] args) {
        int maxLen = 100 ;
        int maxValue = 500 ;
        int testTimes = 10000 ;
        System.out.println("测试开始");
        for (int i = 0 ; i < testTimes ; i++){
            int [] arr = randomArray(maxLen , maxValue);
            int ans = oneMindIndex(arr) ;
            if (!check(arr , ans)){
                printArray(arr);
                System.out.println(ans);
                break;
            }
        }
        System.out.println("测试结束");
    }

    // 测试方法 传入数组和你认为的局部最小值
    public static boolean check (int[] arr , int minIndex){
        if (arr.length == 0){
            return minIndex == -1 ;
        }
        // 左边的数
        int left = minIndex - 1 ;
        // 右边的树
        int right = minIndex + 1 ;
        // 检测 左边位置是否越界，不越界比一下， 越界就认为true
        boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true ;
        // 检测 右边位置是否越界，不越界比一下， 越界就认为true
        boolean rightBigger = right < arr.length ? arr[right] > arr[minIndex] : true ;
        // 俩全为 true 才是 true
        return leftBigger && rightBigger ;
    }

    // 打印数组
    public static void printArray(int[] arr){
        for (int num : arr){
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // 根据传入的最大值和最大长度，生成随机数组，无序，相邻不等
    public static int[] randomArray(int maxLen , int maxValue){
        int len = (int) (Math.random() * maxLen) ;
        int[] arr = new int[len] ;
        if ( len > 0 ) {
            arr[0] = (int) (Math.random() * maxValue) ;
            for (int i = 1 ; i < len ; i++) {
                do {
                    arr[i] = (int) (Math.random() * maxValue);
                }
                // 如果相邻数相当就重做，保证相邻不等
                while (arr[i] == arr[i - 1]);
            }
        }
        return arr ;
    }

    //  传入一个随即数组(无序,相邻不等)，返回一个局部最小值
    public static int oneMindIndex( int [] arr ){
        // 处理边界，如果数组为空  或  长度为0   就返回-1  表示 没有
        if ( arr == null || arr.length == 0){
            return -1 ;
        }
        int N = arr.length ;
        // 如果 长度为1 ，就返回0位置
        if (N == 1) {
            return 0 ;
        }
        // 如果第一个数小于第二个数，返回第一个数
        if (arr[0] < arr[1]) {
            return 0 ;
        }
        // 如果最后一个数小于倒数第二个数，返回最后一个数
        if (arr[N - 1] < arr[N - 2]){
            return N-1 ;
        }
        // 开始位置
        int L = 0 ;
        // 结束位置
        int R = N - 1 ;
        while (L < R - 1) {
            // 设置中点
            int mid = (L + R) / 2 ;
            // 如果中点位置同时小于两边  直接返回中点位置，退出循环
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]){
                return mid ;
            }else{
                // 如果  中点位置比左边数大，砍掉右边  结束位置R来到mid-1位置
                if (arr[mid] > arr[mid - 1]){
                    R = mid - 1 ;
                    // 否则  中点位置比右边数大，砍掉左边  开始位置L来到mid+1位置
                }else{
                    L = mid + 1 ;
                }
            }
        }
        return  arr[L] < arr[R] ? L : R ;
    }
}
